package sit.engreal.leetcode.problems100;

import org.junit.jupiter.api.Assertions;
import sit.engreal.leetcode.util.ListNode;

/**
 * <a href="https://leetcode.cn/problems/merge-two-sorted-lists/"> 21. 合并两个有序链表 </a>
 */
public class LeetCode21 {

    static class Solution {
        public ListNode mergeTwoLists(ListNode p, ListNode q) {
            final ListNode head = new ListNode();
            ListNode tail = head;
            while (p != null && q != null) {
                if (p.val < q.val) {
                    tail.next = new ListNode(p.val);
                    p = p.next;
                } else {
                    tail.next = new ListNode(q.val);
                    q = q.next;
                }
                tail = tail.next;
            }
            p = p == null ? q : p;
            while (p != null) {
                tail.next = new ListNode(p.val);
                p = p.next;
                tail = tail.next;
            }
            return head.next;
        }
    }

    public static void main(String[] args) {
        final Solution solution = new Solution();

        {
            final ListNode p = new ListNode(1, new ListNode(2, new ListNode(4)));
            final ListNode q = new ListNode(1, new ListNode(3, new ListNode(4)));
            final ListNode expect = new ListNode(1, new ListNode(1, new ListNode(2,
                    new ListNode(3, new ListNode(4, new ListNode(4))))));
            final ListNode out = solution.mergeTwoLists(p, q);

            Assertions.assertTrue(ListNode.listEqual(expect, out));

        }

        {
            final ListNode p = null;
            final ListNode q = null;
            final ListNode expect = null;
            final ListNode out = solution.mergeTwoLists(p, q);

            Assertions.assertTrue(ListNode.listEqual(expect, out));

        }

        {
            final ListNode p = null;
            final ListNode q = new ListNode(0);
            final ListNode expect = new ListNode(0);
            final ListNode out = solution.mergeTwoLists(p, q);

            Assertions.assertTrue(ListNode.listEqual(expect, out));

        }

    }
}
